package com.leetcode.problems041;

/**
 * https://leetcode-cn.com/problems/first-missing-positive/
 * @Date 2021/12/09 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {

    public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while(nums[i] > 0 && nums[i] <= nums.length && nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]){
                swap(nums,i,nums[i] - 1);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] != i + 1){
                return i + 1;
            }
        }
        return nums.length + 1;
    }

    /**
     * 数组交换两个位置的数据
     * @param nums
     * @param i
     * @param j
     */
    public void swap(int[] nums,int i,int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }


    public static void main(String[] args) {
        int[] candidates = {3,4,-1,1};
        System.out.println(new Solution().firstMissingPositive(candidates));
    }
}
